#include<vector>
#include<queue>
using namespace std;
class Solution {
private:
    void smallestK(vector<int>& arr, int start,int end,int k) {
        if (k < start || k >= end) return;
        int priv = arr[start];
        int left = start + 1;
        int right = end - 1;
        while (left <= right) {
            if (arr[left] <= priv)
                ++left;
            else
                swap(arr[left], arr[right--]);
        }
        swap(arr[right], arr[start]);
        if (right < k) smallestK(arr, right+1, end, k);
        else if (right > k) smallestK(arr, start, right,k);
    }


public:
    //vector<int> smallestK(vector<int>& arr, int k) {
    //    if (arr.size() <= k) return arr;
    //    priority_queue<int>queue;
    //    for (int i = 0; i < arr.size(); ++i) {
    //        while (!queue.empty() && queue.size()>=k&& queue.top() > arr[i])
    //            queue.pop();
    //        if (queue.size() < k)
    //            queue.emplace(arr[i]);
    //    }
    //    vector<int> res;
    //    while (!queue.empty()) {
    //        res.emplace_back(queue.top());
    //        queue.pop();
    //    }

    //    return res;
    //}

    vector<int> smallestK(vector<int>& arr, int k) {
        if (arr.size() <= k) return arr;
        smallestK(arr, 0, arr.size(), k-1);
        return  vector<int>(arr.begin(), arr.begin() + k);
    }
};